package com.snopy.leetcode.index1_1000.index701_800;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author snopy
 * @version 1.0.0
 * @classname Question720
 * @description 词典中最长的单词
 *  给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，
 *  该单词是由 words 词典中其他单词逐步添加一个字母组成。
 *
 * 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
 * 例1：
 * 输入：words = ["w","wo","wor","worl", "world"]
 * 输出："world"
 * 解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。
 * 例2：
 * 输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
 * 输出："apple"
 * 解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"

 * @email 77912204@qq.com
 * @date 2022/03/17 15:13
 */
public class Question720 {
    public static void main(String[] args) {

        String[] arrs = {"a", "banana", "app", "appl", "ap", "apply", "apple","b","ba","ban"};
/*        Arrays.sort(arrs, (o1, o2) -> {
            if (o1.length()!=o2.length()){
                return o1.length()-o2.length();
            }else {
                return o1.compareTo(o2);
            }
        });*/
        String s = longestWord(arrs);
        System.out.println(s);
    }
    public static String longestWord(String[] words) {
        if (words==null || words.length==0){
            return null;
        }
        Set<String> set = new HashSet<>();
        Arrays.sort(words, (o1, o2) -> {
            if (o1.length() != o2.length()){
                return o1.length()-o2.length();
            }else {
                return o2.compareTo(o1);
            }
        });
        set.add("");
        String maxS = "";
        for (int i = 0;i<words.length;i++){
            String word = words[i];
            if (set.contains(word.substring(0,word.length()-1))){
                set.add(word);
                maxS = word;
            }

        }
        return maxS;
    }
}
